Description

gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。蒟蒻们将
n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同，绳
结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。
不计摩擦，不计能量损失，由于gty足够矮所以不会掉到地上。

Input

输入第一行为一个正整数n(1<=n<=10000)，表示gty的数目。
接下来n行,每行三个整数xi，yi，wi，表示第i个gty的横坐标，纵坐标和重力。
对于20%的数据，gty排列成一条直线。
对于50%的数据，1<=n<=1000。
对于100%的数据，1<=n<=10000,-100000<=xi,yi<=100000

Output

输出1行两个浮点数（保留到小数点后3位），表示最终x的横、纵坐标。

Sample Input

3

0 0 1

0 2 1

1 1 1

Sample Output

0.577 1.000

HINT

Nothing left

Solution

第一次接触模拟退火，还是好好的理一理，其实学长说我们学早了，不过我和**阳都觉得这个蛮有意思的，就试试看QAQ。

首先退火这个名次来源于物理,我们回顾一下历史：

美国物理学家 N.Metropolis 和同仁在1953年发表研究复杂系统、计算其中能量分布的文章，他们使用蒙特卡罗模拟法计算多分子系统中分子的能量分布。这相当于是本文所探讨之问题的开始，事实上，模拟退火中常常被提到的一个名词就是Metropolis准则，后面我们还会介绍。

美国IBM公司物理学家 S.Kirkpatrick、C. D. Gelatt 和 M. P. Vecchi 于1983年在《Science》上发表了一篇颇具影响力的文章：《以模拟退火法进行最优化（Optimization by Simulated Annealing）》。他们借用了Metropolis等人的方法探讨一种旋转玻璃态系统（spin glass system）时，发觉其物理系统的能量和一些组合最优（combinatorial optimization）问题（著名的旅行推销员问题TSP即是一个代表例子）的成本函数相当类似：寻求最低成本即似寻求最低能量。由此，他们发展出以 Metropolis 方法为本的一套算法，并用其来解决组合问题等的寻求最优解。

几乎同时，欧洲物理学家 V.Carny 也发表了几乎相同的成果，但两者是各自独立发现的；只是Carny“运气不佳”，当时没什么人注意到他的大作；或许可以说，《Science》杂志行销全球，“曝光度”很高，素负盛名，而Carny却在另外一本发行量很小的专门学术期刊《J.Opt.Theory Appl.》发表其成果因而并未引起应有的关注。

Kirkpatrick等人受到Metropolis等人用蒙特卡罗模拟的启发而发明了“模拟退火”这个名词，因为它和物体退火过程相类似。寻找问题的最优解（最值）即类似寻找系统的最低能量。因此系统降温时，能量也逐渐下降，而同样意义地，问题的解也“下降”到最值。

关于什么是退火…

其实在热力学上，退火现象是指物体逐渐降温的物理现象，温度越低，自然物体的能量越低，那么分子的运动也相对要稳定，形象的理解为物体分子的运动范围就很小了

而这个性质体现在代码编程中就是搜索的范围是有时间的推移逐渐缩小的。

爬山与模拟退火的区别…

爬山算法基于一种简单的贪心，枚举可行点后，选取一个最优的状态作为当前的解，然后再去搜索其他的解。

很显然，爬山算法只能求的局部最优解，当然如果你的初始状态选得合理，也是可以搜出答案的。

而模拟退火的优越之处，在于他会根据一定的概率来选择当且这个看似不可能成为最优解的答案，这个概率的公式待会再说。如果我们接受了一个“错误答案”，我们就有跳出这个局部的可能，才能搜到正确答案。

如上图中的b点右边的峰值。

一个公式（准则）

这个我就解释不了了，记下来就行了。

根据Metropolis准则，粒子在温度T时趋于平衡的概率为exp(-ΔE/(kT))，其中E为温度T时的内能，ΔE为其改变数,k为Boltzmann常数。Metropolis准则常表示为

Metropolis准则表明，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为：P(dE) = exp( dE/(kT) )。其中k是一个常数，exp表示自然指数，且dE<0。所以P和T正相关。这条公式就表示：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于dE总是小于0（因为退火的过程是温度逐渐下降的过程），因此dE/kT < 0 ，所以P(dE)的函数取值范围是(0,1) 。随着温度T的降低，P(dE)会逐渐降低。

然后我们就可以在(0,1)之间rand一个数，然后如果p(dE)>rand，依旧更新答案，否则舍弃。

SA的实质

其实我们可以从公式或者是待会的代码中发现，模拟退火实际上是把我们需要的目标函数f(x),转化成一个虚拟物体的内能E(x)。经行模拟。

温度是一个很抽象但是和重要的控制参数，它不仅控制着搜索次数，更重要的是它控制着搜索的范围。

神犇的解释：由初始解 i 和控制参数初值 t 开始，对当前解重复“产生新解→计算目标函数差→接受或丢弃”的迭代，并逐步衰减 t 值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值 t 及其衰减因子Δt 、每个 t 值时的迭代次数L和停止条件S。

两句话的总结

对于一个优于当前解的答案，我们必然接受，对于一个不优于当前解的答案，我们以一定概率接受。

所以我们可以看到Simolate Anneal是有可能做不出正解的，所以通常我们会外层循环多次，逼迫其找到最优解。

言归正传

传送门の

大概就是广义上的费马点，我们可以在初始状态选一个点，然后由它开始搜索。
具体的初始温度，和每次温度下降的常数delta，可以根据题目本身和做题经验结合考虑，delta越趋近1，答案往往更精确，但是也付出了时间复杂度的代价。

再一个可能不是太好调试吧23333QAQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <bits/stdc++.h>
using namespace std;
struct Point{
	double x,y;
	Point(double a=0,double b=0):x(a),y(b) {}
};
const int maxn=10005;
const double INF=1e18;
Point p[maxn];
double w[maxn];
Point tar;
double mi=INF;
int n; 
double dist(Point a,Point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double randx(){
	return 1.0*rand()/RAND_MAX;
}
double solve(Point a){
	double res=0;
	for(int i=1;i<=n;i++)res+=w[i]*dist(a,p[i]);
	if(res<mi)mi=res,tar=a;
	return res;
}
void sa(){
	double dE,T=1e5;
	Point a=tar,now;
	while(T>0.001){
		now.x=a.x+T*(randx()*2-1);
		now.y=a.y+T*(randx()*2-1);
		dE=solve(a)-solve(now);
		if(dE>0||exp(dE/T)>randx())
			a=now;
		T*=0.97;
	}
	for(int i=1;i<=1000;i++){
		now.x=tar.x+T*(randx()*2-1);
		now.y=tar.y+T*(randx()*2-1);
		solve(now);
	}
}
int main(){
	srand(20000512);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lf%lf%lf",&p[i].x,&p[i].y,&w[i]);
		tar.x+=p[i].x,tar.y+=p[i].y;
	}
	tar.x/=n,tar.y/=n;
	solve(tar);sa();
	printf("%.3f %.3f\n",tar.x,tar.y);
	return 0;
}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦